package com.wtgroup.demo.leetcode.q022;

import java.util.ArrayList;
import java.util.List;

/**
 * 我的回溯
 *
 * @author dafei
 * @version 0.1
 * @date 2021/4/6 11:07
 */
public class Q022_M2 {

    public static void main(String[] args) {
        int[] inputs = {3, 1};
        Q022_M2 exe = new Q022_M2();
        for (int input : inputs) {
            List<String> ans = exe.generateParenthesis(input);
            System.out.println(ans);
        }
    }

    static final char LP = '(';
    static final char RP = ')';

    public List<String> generateParenthesis(int n) {

        List<String> container = new ArrayList<>();
        StringBuilder buff = new StringBuilder();
        backtrace(container, buff, 0, 2*n, 0, 0);

        return container;
    }

    private void backtrace(List<String> container, StringBuilder buff, int lvl, int lvlLimit, int lpn, int rpn) {
        if (lvl == lvlLimit) {
            // 路径走到底->收集有效解
            container.add(buff.toString());
        } else {
            /*
            * 左分支->阻止左括号过多->确保左括号数<=n
            * 右分支->阻止右括号过多和不成对->确保左括号数>=右括号数
            * */

            // 左分支
            if (lpn < lvlLimit/2) {
                buff.append(LP);
                backtrace(container, buff, lvl + 1, lvlLimit, lpn + 1, rpn);
            }
            // 回溯 -> 右分支
            buff.delete(lvl, buff.length());

            // 右分支
            // 选择右分支->无需防止右括号不够
            if (lpn > rpn) {
                buff.append(RP);
                backtrace(container, buff, lvl + 1, lvlLimit, lpn, rpn + 1);
            }
        }
    }
}
